package src.sort;

public class Insert {

    /**
     * 插入排序
     * 保证第i次排序中，前面的都是有序的。将第i个插入后保证依旧有序
     */
    public static void sort(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {

            //cur为插入的数的位置
            int cur = i;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[cur] < nums[j]) {
                    Utils.swap(nums, cur, j);
                    cur = j;
                }else {
                    break;
                }
            }
        }
    }


    /**
     * 找到位置后在进行插入、后移操作
     * @param nums
     */
    public static void sort1(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {

            //cur为将要插入的位置
            int cur = i;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] > nums[i]){
                    cur = j;
                }
            }

            int pos = nums[i];
            for (int j = i - 1; j >= cur; j--) {
                Utils.swap(nums, j+1, j);
            }
            nums[cur] = pos;
        }
    }


    /**
     * 找到位置后在进行插入、后移操作
     * 用二分查找寻找插入位置
     * @param nums
     */
    public static void sort2(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {

            int left = 0, right = i - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if(nums[mid] > nums[i]) right = mid - 1;
                else left = mid + 1;
            }

            int temp = nums[i];
            for (int j = i - 1; j >= left; j--) {
                Utils.swap(nums, j+1, j);
            }
            nums[left] = temp;
        }
    }


    /**
     * 2-路插入排序
     * 新建一个数组，将0作为中间数，比之大的往0的右边放，比之小的往i的左边放
     * TODO
     * @param nums
     */
    public static void sort3(int[] nums) {

    }


    /**
     * 表插入排序
     * TODO
     * @param nums
     */
    public static void sort4(int[] nums) {

    }
}
